package zty.structures.linkedlist;


/**
 * 带头结点单链表实现
 * 数据从尾部添加
 * @author tyzhang
 * @Date: 2021/2/22 9:17
 */
public class SingleLinkedList {
    public static void main(String[] args) {

        OnePieceNode piece1 = new OnePieceNode(1000,"路飞","超人系");
        OnePieceNode piece2 = new OnePieceNode(999,"索隆","剑士");
        OnePieceNode piece3 = new OnePieceNode(1234,"乔巴","动物系");
        OnePieceNode piece4 = new OnePieceNode(222,"娜美","航海士");
        OnePieceNode piece5 = new OnePieceNode(10000,"路飞qq","觉醒超人系");

        SingleLinked onePiece = new SingleLinked();

//        onePiece.addNode(piece1);
//        onePiece.addNode(piece2);
//        onePiece.addNode(piece3);
//        onePiece.addNode(piece4);
//        System.out.println("排序前榜单:");
//        onePiece.showList();

        onePiece.addNodeByMoney(piece1);
        onePiece.addNodeByMoney(piece2);
        onePiece.addNodeByMoney(piece3);
        onePiece.addNodeByMoney(piece4);
        System.out.println("排序后榜单:");
        onePiece.showList();

        System.out.println("榜单大小：" + SingleLinkedList.getLinkedSize(onePiece.getHead()));
        System.out.printf("倒数第{%d}个海贼为：%s\n",3,SingleLinkedList.getNode(onePiece,1).toString());

        System.out.println("反转后的榜单：");
        SingleLinkedList.reversalNode(onePiece.getHead());

//        onePiece.updateNode(piece5);
//        System.out.println("修改后数据");
//        onePiece.showList();
//
//        onePiece.deleteNode("乔巴11");
//        System.out.println("删除后数据");
//        onePiece.showList();

    }

    /**
     * 1) 求单链表中有效节点的个数
     * @param head 链表的头结点
     * @return 个数
     */
    public static int getLinkedSize(OnePieceNode head){
        if (head.next == null){
            System.out.println("链表为空！");
            return 0;
        }
        int count = 0;
        OnePieceNode node = head.next;
        while (node != null){
            count++;
            node = node.next;
        }
        return count;
    }

    /**
     * 2) 查找单链表中的倒数第 k 个结点
     * 设置两个快慢指针，前和后两个指针间隔 index
     * 当快指针到尾时，慢指针指向的就是所需要的
     * @param singleLinked 链表
     * @param index 倒数第{index}个下标
     * @return 返回结果
     */
    public static OnePieceNode getNode(SingleLinked singleLinked,int index){
        if (singleLinked.getHead().next == null){
            return null;
        }
        int count = 0;
        OnePieceNode temp = singleLinked.getHead();
        OnePieceNode frontTemp = temp;
        OnePieceNode backTemp = singleLinked.getHead();
        while (frontTemp.next != null){
            if (count != index - 1){
                count++;
                frontTemp = frontTemp.next;
            }else {
                frontTemp = frontTemp.next;
                backTemp = backTemp.next;
            }
        }
        return backTemp;
    }

    /**
     * 3) 单链表的反转
     * @param head 要反转的链表节点
     */
    public static void reversalNode(OnePieceNode head){
        if (head.next != null) reversalNode(head.next);
        System.out.println(head.toString());
    }

}

/**
 * 单链表相关操作
 */
class SingleLinked{

    private final OnePieceNode head = new OnePieceNode(0,"","");

    public OnePieceNode getHead() {
        return head;
    }

    /** 尾插法，添加节点 */
    public void addNode(OnePieceNode node){
        OnePieceNode temp = head;
        while (true){
            if (temp.next != null){
                temp = temp.next;
            }else {
                temp.next = node;
                break;
            }
        }
    }

    /**比较赏金插入数据 */
    public void addNodeByMoney(OnePieceNode node){
        OnePieceNode temp = head;
        while (true){
            if (temp.next == null){
                temp.next = node;
                break;
            }else if (temp.next.money > node.money){
                node.next = temp.next;
                temp.next = node;
                break;
            }
            temp = temp.next;
        }
    }

    /** 修改节点 */
    public void updateNode(OnePieceNode node){
        OnePieceNode temp = head;
        if (temp.next == null){
            System.out.println("链表为空！");
        }else {
            while (true){
                if (temp.next == null){
                    System.out.printf("海贼榜中不存在%s",node.name);
                    break;
                }else if (temp.name.equals(node.name)){
                    temp.money = node.money;
                    temp.ability = node.ability;
                    break;
                }
                temp = temp.next;
            }
        }
    }

    /** 删除节点 */
    public void deleteNode(String name){
        OnePieceNode temp = head;
        if (temp.next == null){
            System.out.println("海贼榜中无数据！");
        }else {
            while (true){
                if (temp.next == null){
                    break;
                }
                if (temp.next.name.equals(name)){
                    temp.next = temp.next.next;
                    break;
                }
                temp = temp.next;
            }
        }
    }

    /** 查看海贼榜 */
    public void showList(){
        if (head.next == null){
            System.out.println("海贼榜为空");
        }
        OnePieceNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
}



/**
 * 单链表头结点
 */
class OnePieceNode{
    /** 赏金、名字、能力 */
    public int money;
    public String name;
    public String ability;
    public OnePieceNode next;

    public OnePieceNode(int money, String name, String ability) {
        this.money = money;
        this.name = name;
        this.ability = ability;
    }

    @Override
    public String toString() {
        return "OnePieceNode{" +
                "money=" + money +
                ", name='" + name + '\'' +
                ", ability='" + ability + '\'' +
                '}';
    }
}
